package com.learn.algorithm.dynamic.programming;

public class LeetCode115 {

    public static int numDistinct(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = -1;
            }
        }
        return f(text1.toCharArray(), text2.toCharArray(), n, m, dp);
    }

    public static int f(char[] s, char[] t, int len1, int len2, int[][] dp) {
        if (len1 == 0 && len2 == 0) {
            return 1;
        }
        if (len1 == 0) {
            return 0;
        }
        if (len2 == 0) {
            return 1;
        }
        if (dp[len1][len2] != -1) {
            return dp[len1][len2];
        }
        int ans;
        ans = f(s, t, len1 - 1, len2, dp);
        if (s[len1 - 1] == t[len2 - 1]) {
            ans += f(s, t, len1 - 1, len2 - 1, dp);
        }
        dp[len1][len2] = ans;
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(numDistinct("rabbbit", "rabbit"));
        System.out.println(numDistinct("babgbag", "bag"));
    }
}
